Crypto系列--[DSA]
[DSA]P1
- 加密
\(s = (h + x*r) * invert(k, q) \pmod{q}\)
- 解密
$h = sk - xr $
from Crypto.Util.number import *
x = 744392159315109570754116310771983851757551344975
res = '165782721341339198412647993666509464235357438316955509380916536942999719934859010719239181505641131541336732746487869057254501408932088525210132219812538680103588209858056965704513469397456062462997922579153889365949881483945374353249663615049625464936863731146786939940008455162889222224637559655206650740263,1298650860243423121422960080767774504714070643307,111120374776599326576102904326033963036086162316292379631154390419503544061132194157167377090305717398988633361879833651682909127515227791094298812966962611270373961642366936114520363598605101136319314592110825225829682824742733558890102442848946833269792264526631952031522242050722574666760289342904184078147,58676530010022270392556756451520166345533492569982892999884013280223267213196327908109838779404799027430871002478198309765681524297432684079224431376866288514458611451837344124101552983430964624885275562335163386558368543421816902968921004905903289705261286520219762327567450079657631837085261332809902779541,1202934132268354747046504251953952503269375110119,556505026580608336190454039247331999698427391838,643380837304587319829716195016078835692377111801'
res = res.split(',')
a = 'p,q,g,y,k,r,s'
a = a.split(',')
print(a)
data = {}
for i in range(7):
data[a[i]] = int(res[i])
print(data)
# s*k = h + x*r mod q
s = data['s']
k = data['k']
r = data['r']
q = data['q']
m = (s*k - x*r)%q
flag = long_to_bytes(m)
print(flag)[DSA]P2
- 离散对数问题
\(g^{x} \pmod{p} = y\)
sympy脚本
from sympy import *
p = 8361306460427
g = 1772320310198
y = 4940794325855
# y = powmod(g, x, p)
m = discrete_log(p,y,g) # 模 余 底
m = str(m).encode()
flag = b'NSSCTF{'+ m + b'}'
print(flag)sage脚本1
p = 8361306460427
g = 1772320310198
y = 4940794325855
# y = powmod(g, x, p)
m = discrete_log(y,mod(g,p)) # 余 底
m = str(m).encode()
flag = b'NSSCTF{' + m + b"}"
print(flag)sage脚本2
p = 8361306460427
g = 1772320310198
y = 4940794325855
# y = powmod(g, x, p)
F = GF(p) # 关于GF # https://bbs.ctf.show/thread/68
g = F(g)
y = F(y)
m = discrete_log(y,g)
m = str(m).encode()
flag = b'NSSCTF{' + m + b"}"
print(flag)[DSA]P3
- 离散对数问题，限定范围的x
# sage
p = 170348437069105675857023420369852707107199919792133184452360056253809337668300908125853674590750392947050710727732463955472261258268602007044222277390154053179972622853725777103969911116086298972690976389030851269618265250128626615573340600153282617025741773802362792814749643535242494474688828746111924564347
g = 165897807691210138242402562954872978913428506002086890183488722074489316352258963927481837058576723028094761779902049658188277585007037781070468378089752847174284810042043509739186585150021863898785139309655899362319277284062985948365352003897500446368706636436322274748243327625738381556542611629507069843590
y = 137261382691605813386002060971037192576990902114543987122319043412750149427553984596309208612435032869944636556014997562080112842853873993200670664292253373789312207761559974016876136547508448082441175904892258008489730428622596221443832423875069612364113749289160065933164504747254869418301359752739411555852
# y = powmod(g, x, p)
F = GF(p)
g = F(g)
y = F(y)
m = discrete_log_lambda(y,g,(2^39,2^40)) # 余 底 x范围
m = str(m).encode()
flag = b'NSSCTF{' + m + b"}"
print(flag)[DSA]P4
- 已知K攻击
from Crypto.Util.number import *
from gmpy2 import *
k = 516081660287290857303106041337362876434325919397
p, q, g, y, h, r, s = [180085593791508295346273423844236672339529319991924110327255270917858493493345299800615314524299320066806895354429976173332282295460587950377809600292446537411907628568599603375827769404064672706774870194085492090905235979942093907713387405089913530830285562903861798734400682400477696202626239784027815756743,1104557835344327388179959575459485168270179811873,12123130287415691980412799115852211438041361537629665887505875653480334758768653356186670191369220495071169163684628920472799820550702077504266995537429931375859921727628448675950283799950650147579085064551465705638988147809494939857856057753379728219901701640783558562051528103036368234500856431719560283977,153241032666637708500087115670945288942606390433856489794132009126475826308531535572154555100639916171117128048502364849141148971767208837503665967407569265064568891309540988565553839914146806227763059644757144119318730674662405727893965437702774458275036467867455574739153189363237418960939893039809283051396,1385824418563203380722890100218787157930069255720,183925646270847239867260215378432900916502633028,436799484642842219800973572361673811756031905793]
x = ( s * k - h ) * invert(r,q)%q
m = long_to_bytes(x)
flag = b'NSSCTF{' + m + b'}'
print(flag)[DSA]P5
- K爆破攻击
\(k = random.randint(1, 2^{20})\)
密文是uuid形式的
from Crypto.Util.number import *
from libnum import *
from gmpy2 import *
p, q, g, y, h, r, s = [232417151883368054516605830055952160880670978405659642430490266526812173832260694367747527073710881837011446979721612305292421320659024746677762768546062204667982434421909069699232443934954948621989591579797868456092114070836952969434575376001506929674552348068770008372122577006292508896861736763536866927803,1060620588842972438899442975440075622760455989309,44768917997338391084473070795826454686235133633449491548990823774293785572926447629504858779348089685405258929615166589878059445496157877609271409247291851051458981907101186579608794375285071749267992568084274340113631398343686417217303951367225442028660036057697482769986378944452588020590255584155269256494,15138996987998119707598289320039109142321006894939822519880182224518520081477043981280071391740009592471003140567144801380938339219351181199631326928072076701047098027574156016825986846074561729606049521802900128625422690773497399889659856302120776644163941218439800480424839747421786767043056933847090680182,1234324463386109858490857668286337914111126412605,83059873905640807538034110870406547173849277486,1037113405299161333909263662048616171640477800689]
r = invert(r,q)
# for i in range(2,2^20):
for i in range(2,2^20):
temp = ( s*i - h )*r % q
v = n2s(int(temp))
if v.count(b'-') == 2 and len(v)<20:
print(v)
# d2d2f3db-f44b-41c7[DSA]P6
- K共享攻击
from Crypto.Util.number import *
from gmpy2 import *
p, q, g, y = 210145691501773578738377348033311975109097030624229264466788375283767533919326464465174636163332688722224581089450096402386769629298291083760904660611942708672827379160413284668161925839781496461631351601204438246469229385099502482935026018822981911090812522940670041497153171870525509599105379465080807836739,1198259187878727821038260641949026509111920270433,196070047258907618917994526171930725445041293594930451395813866076072912063450682578080857729624238303488600108328510272125657269217146364809009485238108834676036204139548225631723795405961936284355847299908680455823548490632994637690236187388967162639874250381038952479751971000815634264164616859879415711204,113892660154815927896065262713895897930759494276164055918916161302422466569511088272910136873131800900714081704069756811621255412857706485959053239368822240528099295009222226245910132521725945595438150866573053321959800267582969690297868819195328552315818030736239776841162267931134372314713955308734418315441
(h1, r1, s1) = 288608925920757761908146359265652114672439915971, 70578181835631077171027353972389074292538336310, 10138006399945530096316239936933893062913122896
(h2, r2, s2) = 292826952671130597654686220387088149924959682815, 70578181835631077171027353972389074292538336310, 601690991376973737187439170192344609140533841457
# (s1-s2)*k = h1 - h2 %q
k = (h1-h2)*invert(s1-s2,q)%q
x = ( s1 * k - h1 ) * invert(r1,q)%q
m = long_to_bytes(x)
flag = b'NSSCTF{' + m + b'}'
print(flag)[DSA]P7
- 线性K攻击
\(s_1 * k_1 = h_1 + x*r_1 \pmod{q}\)
\(s_2 * (123123k_1 + 213123) = h_2 + x*r_2 \pmod{q}\)
x未知，构造\(x*r_1*r_2\)消元
\(s_1 * k_1 * r_2 = h_1*r_2 + x*r_1*r_2 \pmod{q}\)
\(s_2 * (123123k_1 + 213123)*r_1 = h_2*r_1 + x*r_2*r_1 \pmod{q}\)
相减只有一个未知数
\(k_1 \equiv\)\(h_2*r_1 - h_1*r_2 - s_2*213123*r_1\over{s_2*r_1*123123 - s_1*r_2}\)\(\pmod{q}\)
from Crypto.Util.number import *
from gmpy2 import *
from libnum import *
p, q, g, y = 248604602422910519027498055793201627104398247250051630675851204123046532565091226817355596701504144088229653099743376808895289529496613830342512762129413510736292280512125238597842272278759062316841642879931389189133077729867472969222059167595875408174942099331637968192646102751148170581062955479624795726803,1104888844039545494900451432921843691528361275421,179257043110102699137458477420103918554872480317804287592976758715562911175633485646459879116166908433112797107120185385797578936816467598792615613604506581942838034541566199558185747738124918980520382612117236824821289695971682490339435434475068166996448327818163252231908864987994621701200833277417006819871,159005646554391816923406887830979293509940608900317516799440723663025433835806129396573183140255812264469834382283265708315756408213239261422711978866078853083466087419416562334241054267280145144390020259686908268717687033486580768464112616050989149109970819378634556467410938187635262996429292198522330176893
(h1, r1, s1) = 1120509804671964533658263171593312514868852942664, 1092962395012982010125401435695438064740884031414, 870170073609429297690585216747619586014108208356
(h2, r2, s2) = 656005973206825385654744797203106611919992582404, 670071713626039247317315700175834986360787995677, 628224540815786948931138021701729862880600004465
# k1 = getPrime(64)
# r1 = powmod(g, k1, p) % q
# s1 = (h1 + x*r1) * invert(k1, q) % q
# k2 = 123123*k1 + 213123
# r2 = powmod(g, k2, p) % q
# s2 = (h2 + x*r2) * invert(k2, q) % q
k = (h2*r1 - h1*r2 - s2*213123*r1) * inverse(s2*123123*r1 - s1*r2,q)%q
print(k)
m = (s1*k - h1) * invert(r1,q) % q
flag = n2s(int(m))
print(flag)[DSA]P8
- 关系K攻击
\(s_1*k_1 \equiv m_1 + x*r_1 \pmod{q}\)
\(s_2*k_1^{2} \equiv m_2 + x*r_2 \pmod{q}\)
x未知，构造\(x*r_1*r_2\)消元
\(s_2*k_1^{2}*r_1 - s_1*k_1*r_2 \equiv m_2*r_1 - m_1*r_2 \pmod{q}\)
只有一个未知数，有限域内求解
\(f = s_2*k_1^{2}*r_1 - s_1*k_1*r_2 - m_2*r_1 + m_1*r_2\)
from Crypto.Util.number import *
from gmpy2 import *
from libnum import *
p, q, g, y = 149328490045436942604988875802116489621328828898285420947715311349436861817490291824444921097051302371708542907256342876547658101870212721747647670430302669064864905380294108258544172347364992433926644937979367545128905469215614628012983692577094048505556341118385280805187867314256525730071844236934151633203,829396411171540475587755762866203184101195238207,66574026244680091069518316704198662248616273869450543744119730925010741440009253221024269611702409992941009990810332788277765645172259247006372628490621965540198848398426564970679555614131868432980284836439911133867262442690193568710848637395672849408343310213459158340521055585119320384998345666167582343319,113160705347753807573510544961675737216163465780410091146961355899888740070887609372690358436441644814541660853774651122835982545831124611677315480368181887207540230682166723644914975259836636643623433521449469020855846403587460946141523029279424148079870427795307567353090927085416942020200370785081813797653
(h1, r1, s1) = 592632528802360292619666791193487295190074169778, 795968565942507694843762914966982971870045417145, 487794348943414262409771614228723658312500553511
(h2, r2, s2) = 1058580579731370773060403038853538332541169097744, 583365243104095833266690387387608816520877657593, 382650490310903109923939919364642244260295044662
# k1 = getPrime(64)
# r1 = powmod(g, k1, p) % q
# s1 = (h1 + x*r1) * invert(k1, q) % q
# k2 = k1**2
# r2 = powmod(g, k2, p) % q
# s2 = (h2 + x*r2) * invert(k2, q) % q
PR.<x> = PolynomialRing(GF(q))
f = s2*x^2*r1 - s1*x*r2 - h2*r1 + h1*r2
hh = f.roots()
print(hh)
k = hh[1][0]
x = (s1*k - h1)*inverse(r1,q)%q
flag = n2s(int(x))
print(flag)
